﻿// 328. 电路板 Bridging signals（挑战程序设计竞赛）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <memory.h>
using  namespace std;


/*

https://www.papamelon.com/problem/328



在电路板的一侧有 1,2,3,...,n 共 n 个端口, 另一侧亦然。每个左侧的端口通过一条线和右边的某条端口连接起来。
电路板设计时考虑不周，因此有些连线交叉，现在需要保留一些电线在电路板上(保留下来的电路板上的连线不能有交叉)。
求能留在电路板上的电线的数量的最大值。

输入
第一行输入一个整数 T，表示测试数据的组数
每组测试数据如下：
第一行包括一个整数 n
接下来的 n 行每行包含一个整数 x，第 i 个数表示左边的第 i 个端口应该与右边的第 x 个端口进行连接
1≤n,x≤40000
输出
对于每组测试用例，输出一行，一个整数，表示答案
样例 1
输入
4
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
8
8
7
6
5
4
3
2
1
9
5
8
9
2
3
1
7 
4
6
输出
3
9
1
4
*/


const int N = 40010;
int dp[N];
int arr[N];
int t, n;

int bsearch(int x, int r) {
	int l = 1;
	while (l < r) {
		int mid = (l+r )>> 1;
		if (dp[mid]  >= x) r = mid;
		else l = mid + 1;
	}

	return l;
}


void solve() {
	memset(dp,0,sizeof dp);
	memset(arr,0,sizeof arr);
	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> arr[i]; }

	int idx = 1; dp[idx] = arr[idx];

	for (int i = 2; i <= n; i++) {
		if (arr[i] > dp[idx]) {
			dp[++idx] = arr[i];
		}
		else {
			int pos = bsearch(arr[i], idx);
			dp[pos] = arr[i];
		}
	}

	for (int i = n; i >= 0; i--) {
		if (dp[i] != 0) {
			cout << i << endl;
			break;
		}
	}
	return ;
}


int main()
{
	cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}
 